package cn.edu.jxau.test;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 付大石
 */
public class Sort {

    public static void main(String[] args) throws IOException {

//        int len = 10000;
//        int[] arr = new int[len];
//        DataInputStream in = new DataInputStream(new FileInputStream("C:\\Users\\PC-Clive\\Desktop\\data.dat"));
//        for (int i = 0; i < arr.length; i++) {
//            arr[i] = in.readInt();
//        }
//        in.close();

        int[] arr = { 2, 3, 5, 7, 3, 6, 8, 2, 6, 9, 5, 7, 4, 3, 6, 8, 9, 4, 7, 4, 8, 3, 8, 3 };
        System.out.println(Arrays.toString(arr));
        long start = System.nanoTime();
        sort(arr);
        long end = System.nanoTime();
        System.out.println(Arrays.toString(arr));
        System.out.println("spend tiem:" + (end - start));
    }

    /**
     * 基数排序
     * @param arr
     */
    private static void sort(int[] arr) {

        final int N = 3; // 键值的最大位数
        List<Integer>[] bucketArr = new ArrayList[10];

        // 初始化桶 //
        for (int i = 0; i < bucketArr.length; i++) {
            bucketArr[i] = new ArrayList<Integer>();
        }
        
        // 开始排序 //
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j < arr.length; j++) {
                int w = getWeight(arr[j], i);
                bucketArr[w].add(arr[j]);
            }
            int k = 0;
            for (int j = 0; j < bucketArr.length; j++) {
                List<Integer> list = bucketArr[j];
                for(Integer item : list) {
                    arr[k++] = item;
                }
                list.clear();
            }
        }
    }

    /**
     * 获取一个整数右起第{@code i}位的权值
     */
    private static int getWeight(int num, int i) {

        if (i == 0) {
            throw new IllegalArgumentException("参数i必须大于零");
        }

        i = (int) Math.pow(10, i) / 10;
        return num / i % 10;
    }
}
